package com.zhupf.binaryTree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhupf
 * @date 2023年11月27日 13:28
 * @Description
 *
 * 102. 二叉树的层序遍历
 */
public class LevelOrder {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3,new TreeNode(9),new TreeNode(20,new TreeNode(15),new TreeNode(7)));
        LevelOrder levelOrder = new LevelOrder();
        System.out.println(levelOrder.levelOrder(root));
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stk = new LinkedList<>();
        stk.offer(root);
        while (!stk.isEmpty()){
            int size = stk.size();
            List<Integer> list = new ArrayList<>();
            while (size>0){
                TreeNode node = stk.poll();
                list.add(node.val);
                if(node.left != null){
                    stk.offer(node.left);
                }
                if(node.right != null){
                    stk.offer(node.right);
                }
                size --;
            }
            res.add(list);
        }
        return res;
    }

}
